package com.lun.medium;

import com.lun.util.BinaryTree.TreeNode;

public class SumOfNodesWithEvenValuedGrandparent {
	
	//方法一：自己写的，DFS
    public int sumEvenGrandparent(TreeNode root) {
    	if(root == null) return 0;
    	int result = 0;
    	if((root.val & 1) == 0) {
    		TreeNode left = root.left;
    		if(left != null) {
    			if(left.left != null)
    				result += left.left.val;
    			if(left.right != null)
    				result += left.right.val;
    		}
    		
    		TreeNode right = root.right;
    		if(right != null) {
    			if(right.left != null)
    				result += right.left.val;
    			if(right.right != null)
    				result += right.right.val;
    		}
    	}
    	return result + sumEvenGrandparent(root.left) + sumEvenGrandparent(root.right);
    }
    
    
    //方法二：别人写的，DFS
    public int sumEvenGrandparent2(TreeNode root) {
        return helper(root, 1, 1);
    }

    public int helper(TreeNode node, int p, int gp) {
        if (node == null) return 0;
        return helper(node.left, node.val, p) + helper(node.right, node.val, p) + (gp % 2 == 0 ? node.val : 0);
    }
    
}
